LeetCode 75 Level 1 - Day 4 Linked List

876. Middle of the Linked List

• 題目連結
• 難易度：Easy

題目敘述

Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.

預設函數

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){

}

題目限制

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

解題過程及程式碼

本題是linked list的第3題，題目是輸入1個linked list，要回傳這個linked list最中央的節點，如果中央節點有2個，則回傳第二個，如下圖Fig. 1所示，當節點數量是奇數時回傳最中間的節點，當節點數量是偶數時回傳右邊那個節點。

• 解題想法是遍歷所有節點來計算節點數量 (假設為n)，順便把節點資料丟到array裡面，在判斷節點數量是奇數還是偶數後，直接回傳中央節點
  • 若是奇數則Middle numble index = n / 2 (例如在圖Fig. 1裡，5 / 2 = 2)
  • 若是偶數則index = n / 2 (例如在圖Fig. 1裡，6 / 2 = 3)
• 程式碼上傳：

  struct ListNode* middleNode(struct ListNode* head){
      struct ListNode* ptr_array[100] = {NULL};
      struct ListNode* ptr;
      int index = 0;
  
      ptr = head;
  
      while (ptr != NULL) {
          ptr_array[index] = ptr;
          index++;
          ptr = ptr->next;
      }
  
      return ptr_array[index / 2];
  }
  

今天發文滿一週了，謝謝大家!